/*
 * @lc app=leetcode.cn id=6 lang=cpp
 *
 * [6] Z 字形变换
 */

// @lc code=start
class Solution
{
public:
    string convert(string s, int numRows)
    {
        int n = s.size();
        if (numRows == 1 || numRows >= n)
        {
            return s;
        }
        int cycle = 2 * numRows - 2;
        int cols = (n + cycle - 1) / cycle * (numRows - 1);
        vector<string> matrix(numRows, string(cols, 0));
        for (int i = 0, x = 0, y = 0; i < n; i++)
        {
            matrix[x][y] = s[i];
            if (i % cycle < numRows - 1)
            {
                x++;
            }
            else
            {
                x--, y++;
            }
        }

        string ans;
        for (auto &row : matrix)
        {
            for (auto ch : row)
            {
                if (ch)
                {
                    ans += ch;
                }
            }
        }

        return ans;
    }
};
// @lc code=end
